package algorithms.a05binarysearchtree;

import algorithms.a03sortadvance.QuickSort;
import algorithms.utis.SortTestHelper;

/**
 * 二分查找
 * 只能在有序数组中使用
 * @author 王昊然
 * @create 2018-02-13 22:54
 **/
public class BinarySearch {

    /**
     * 二分查找
     *
     * @param arr    从小到大排列的有序数组
     * @param target
     * @date: 2018/2/13 22:58
     * @author: 王昊然
     */
    public static int find(Comparable[] arr, Comparable target) {

        int n = arr.length;

        int l = 0;
        int r = n - 1;
        int middle = (l + r) / 2;

        while (l <= r) {
            if (arr[middle].compareTo(target) == 0) {
                return middle;
            } else if (arr[middle].compareTo(target) < 0) {
                l = middle + 1;
            } else {
                r = middle - 1;
            }

            middle = (l + r) / 2;
        }

        return -1;
    }

    public static int findByRescursive(Comparable[] arr, Comparable target) {

        return recursive(arr, 0, arr.length - 1, target);
    }

    private static int recursive(Comparable[] arr, int left, int right, Comparable target) {

        if (left > right) return -1;

        int middle = (left + right) / 2;

        if (arr[middle].compareTo(target) == 0) {
            return middle;
        } else if (arr[middle].compareTo(target) < 0) {
            left = middle + 1;
            return recursive(arr, left, right, target);
        } else {
            right = middle - 1;
            return recursive(arr, left, right, target);
        }
    }


    public static void main(String[] args) {
        int N = 10000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        QuickSort.sort(arr);

        System.out.println(find(arr, arr[77]));
        System.out.println(findByRescursive(arr, arr[77]));
    }


}
